package com.mxw.算法之美.a9二叉树;

import com.mxw.leetcode.C1二叉树.entity.TreeNode;

/**
 * @author Administrator
 * @create 2024/7/29 11:14
 */
public class a02二叉查找树 {

    /**
     *  二叉查找树：左子树的每个节点的值，都要小于当前节点的值，而右子树节点的值都大于当前节点的值。类似于当前节点是划分大小的节点，比它小的在左边，比它大的在右边
     */

    /**
     * 查找操作
     */
    public TreeNode search(TreeNode root, int data) {
        while (root != null) {
            if (data < root.val) {
                root = root.left;
            } else if (data > root.val) {
                root = root.right;
            } else {
                return root;
            }
        }
        return null;
    }

    /**
     * 插入操作:
     * 如果插入的数据比节点的数据大，并且节点的右子树为空，将新数据直接插到右子节点的位置。如果不为空，递归遍历右子树，查找插入位置。
     * 同理左边的也是。
     */
    public TreeNode insert(TreeNode root, int data) {
        if (root == null) {
            return new TreeNode(data);
        }
        while (root != null) {
            if (data > root.val) {
                // 右边
                if (root.right == null) {
                    root.right = new TreeNode(data);
                    return root;
                }
                root = root.right;
            } else {
                // 左边
                if (root.left == null) {
                    root.left = new TreeNode(data);
                    return root;
                }
                root = root.left;
            }
        }
        return root;
    }

    /**
     * 删除操作：
     * 1. 如果删除的节点没有子节点，父节点指向删除的节点指针为null
     * 2. 如果删除的节点有1个节点，父节点指向删除的节点指针指向删除节点的子节点
     * 3. 如果删除的节点有2个节点，找到右子树最小的节点，替换到删除的节点位置，然后删除右子树最小的节点
     */
    public void delete(TreeNode root, int data) {
        TreeNode tempParent = null;
        while (root != null && root.val != data) {
            tempParent = root;
            if (data > root.val) {
                // 大于
                root = root.right;
            } else {
                root = root.left;
            }
        }
        if (root == null) {
            return;
        }
        // 删除的节点有两个子节点
        if (root.left != null && root.right != null) {
            // 查找右子树最小节点
            TreeNode minNode = root.right;
            TreeNode minParentNode = root;
            while (minNode.left != null) {
                minParentNode = minParentNode;
                minNode = minNode.left;
            }
            // 将右子树最小节点的值替换到删除节点的位置
            root.val = minNode.val;
            // 删除右子树最小节点
            root = minNode;
            tempParent = minParentNode;
        }

        // 删除节点是叶子节点或这个节点只有一个子节点
        TreeNode child;
        if (root.left != null) {
            child = root.left;
        } else if (root.right != null) {
            child = root.right;
        } else {
            child = null;
        }

        if (tempParent == null) {
            root = child;
        } else if (tempParent.left == root) {
            tempParent.left = child;
        } else {
            tempParent.right = child;
        }
    }

}
